﻿//911. 在线选举
//给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。
//对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。
//在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
//实现 TopVotedCandidate 类：
//TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。
//int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。


class TopVotedCandidate {
public:
    //nums[i]时刻候选人
    vector<int> tops;
    vector<int> times;
    TopVotedCandidate(vector<int>& persons, vector<int>& times)
    {
        unordered_map<int, int> cnt;
        cnt[-1] = -1;
        int top = -1;
        //person ： 所有票数
        for (auto& p : persons)
        {
            cnt[p]++;
            if (cnt[p] >= cnt[top])
            {
                top = p;
            }
            tops.push_back(top);
        }
        this->times = times;
    }

    int q(int t)
    {
        //t时刻
        int pos = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return tops[pos];
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */